class Solution {
public:
    vector<int> grayCode(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int num = 0;
        vector<int> ans;
        vector<bool> vst(1 << n);

        ans.push_back(num);
        vst[num] = true;
        for (int i = 1; i < (1 << n); ++i) {
            for (int j = 0; j < n; ++j) {
                if (!vst[(num ^ (1 << j))]) {
                    num = num ^ (1 << j);
                    vst[num] = true;
                    break;
                }
            }
            ans.push_back(num);
        }
        return ans;
    }
};
